#include "Scheduler.h"
#include "ITask.h"
#include <stdio.h>

namespace easy2d {

#define RENDER_TASK_ID 1

	Scheduler::Scheduler()
	{
		mTaskList = NULL;
		mFrameList = NULL;
		mRenderTask.pTask = NULL;
		mNextId = RENDER_TASK_ID + 1;
	}

	Scheduler::~Scheduler()
	{
		// release our allocated memory
		TaskInfo * pTaskInfo = mTaskList;
		while (pTaskInfo)
		{
			TaskInfo * pTemp = pTaskInfo;
			pTaskInfo = pTaskInfo->pNext;
			delete pTemp;
		}

		pTaskInfo = mFrameList;
		while (pTaskInfo)
		{
			TaskInfo * pTemp = pTaskInfo;
			pTaskInfo = pTaskInfo->pNext;
			delete pTemp;
		}
	}

	void Scheduler::insertFrameTask(TaskInfo *pTaskInfo)
	{
		//
		// inserted into list in time order
		//
		if (!mFrameList)
		{
			pTaskInfo->pNext = NULL;
			mFrameList = pTaskInfo;
		}
		else if (mFrameList->time.next > pTaskInfo->time.next)
		{
			pTaskInfo->pNext = mFrameList;
			mFrameList = pTaskInfo;
		}
		else
		{
			TaskInfo * pInfo = mFrameList;
			while (pInfo)
			{
				if (pInfo->pNext == NULL)
				{
					pTaskInfo->pNext = NULL;
					pInfo->pNext = pTaskInfo;
					break;
				}
				else if (pInfo->pNext->time.next > pTaskInfo->time.next)
				{
					pTaskInfo->pNext = pInfo->pNext;
					pInfo->pNext = pTaskInfo;
					break;
				}
				pInfo = pInfo->pNext;
			}
		}
	}

	void Scheduler::insertTimeTask(TaskInfo *pTaskInfo)
	{
		//
		// inserted into list in time order
		//
		if (!mTaskList)
		{
			pTaskInfo->pNext = NULL;
			mTaskList = pTaskInfo;
		}
		else if (mTaskList->time.next > pTaskInfo->time.next)
		{
			pTaskInfo->pNext = mTaskList;
			mTaskList = pTaskInfo;
		}
		else
		{
			TaskInfo * pInfo = mTaskList;
			while (pInfo)
			{
				if (pInfo->pNext == NULL)
				{
					pTaskInfo->pNext = NULL;
					pInfo->pNext = pTaskInfo;
					break;
				}
				else if (pInfo->pNext->time.next > pTaskInfo->time.next)
				{
					pTaskInfo->pNext = pInfo->pNext;
					pInfo->pNext = pTaskInfo;
					break;
				}
				pInfo = pInfo->pNext;
			}
		}
	}

	void Scheduler::getNextFrameTask(TaskInfo **ppTaskInfo)
	{
		// return the next frame task. If no frame task is scheduled to run this frame,
		// return null. note that this method REMOVES the task from the list, so the
		// caller is responsible for either adding it back in (rescheduling) or
		// deleting it.
		TaskInfo *pNextTask = mFrameList;
		if (pNextTask && pNextTask->time.next <= mClock.getFrame())
		{
			mFrameList = pNextTask->pNext;
			pNextTask->pNext = NULL;
			*ppTaskInfo = pNextTask;
			return;
		}
		*ppTaskInfo=NULL;
	}

	void Scheduler::getNextTimeTask(TaskInfo **ppTaskInfo)
	{
		// return the next time task. If no time task is scheduled to run this frame,
		// return null. note that this method REMOVES the task from the list, so the
		// caller is responsible for either adding it back in (rescheduling) or
		// deleting it.
		TaskInfo *pNextTask = mTaskList;
		if (pNextTask && pNextTask->time.next <= mClock.getFrameEnd())
		{
			mTaskList = pNextTask->pNext;
			pNextTask->pNext = NULL;
			*ppTaskInfo = pNextTask;
			return;
		}
		*ppTaskInfo=NULL;
	}

	int Scheduler::addTask(TaskType type, int start, int period, int duration, ITask * pTask, void * pUser, int *pID)
	{
		//
		// this schedules a task of the appropriate type (RENDER, FRAME, or TIME). Time tasks and
		// frame tasks are kept in separate lists for ease of handling. Render tasks are stored
		// as a single special-case entry.
		//
		// time and frame tasks have a start time, a duration, and a period.
		// the duration is relative to the start time, except for duration 0 which is a special case.
		// since the scheduler doesn't care about the duration itself, it converts it into an end time
		// and stores that instead. the render task does ignores start/duration/end.
		//
		// pUser is a user data pointer.
		//
		// a unique task id is generated and returned in pID. if you don't care about an ID,
		// pass in NULL instead.
		//
		if (type == TASK_RENDER)
		{
			mRenderTask.pTask = pTask;
			mRenderTask.pUser = pUser;
			mRenderTask.id = RENDER_TASK_ID;
			return 1;
		}
		else
		{
			//
			// Allocating memory like this has high overhead. It would be much better to use a
			// fast allocator which preallocates and/or reuses TaskInfo structures.
			//
			TaskInfo *pTaskInfo = new TaskInfo;

			if (pTaskInfo)
			{
				pTaskInfo->pTask = pTask;
				pTaskInfo->pNext = mTaskList;
				pTaskInfo->status = 0;
				pTaskInfo->id = mNextId++;
				if (pID)
					*pID = pTaskInfo->id;
				pTaskInfo->pUser = pUser;
				pTaskInfo->time.start = start;
				pTaskInfo->time.period = period;
				if (duration == 0)
					pTaskInfo->time.duration = 0; // infinite
				else
					pTaskInfo->time.duration = start + duration - 1; // compute end time
				pTaskInfo->time.next = start;

				//printf("Scheduling %s task %u from %3u to %3u, every %2u %s\n",
				//	type==TASK_TIME?"time ":"frame",
				//	pTaskInfo->id,
				//	pTaskInfo->time.start,
				//	pTaskInfo->time.duration,
				//	pTaskInfo->time.period,
				//	type==TASK_TIME?"ms":"frames");

				if (type == TASK_TIME)
					insertTimeTask(pTaskInfo);
				else if (type == TASK_FRAME)
					insertFrameTask(pTaskInfo);
				return 1;
			}
			else return 0;
		}
	}

	void Scheduler::removeTask(int id)
	{
		//
		// Terminate a task. This is most useful with infinite-duration tasks, but
		// it is also handy to delete finite tasks prematurely. It would be a simple
		// matter to add a "suspend task" option which suspends a task instead of
		// removing it.
		//
		// Terminate marks the task for deletion rather than just removing it,
		// since it may be called while ExecuteFrame is iterating through the list.
		// Marked tasks are swept up at the end of each frame.
		//
		// Since all task ID's are unique, this method stops looking after it finds
		// a matching task.
		// 
		bool found = false;

		if (id == RENDER_TASK_ID)
		{
			mRenderTask.pTask = NULL;
			found = true;
		}

		TaskInfo * pTaskInfo = mTaskList;
		while (pTaskInfo && !found)
		{
			if (pTaskInfo->id == id)
			{
				pTaskInfo->status = TASK_DELETE;
				found = true;
				break;
			}
			pTaskInfo = pTaskInfo->pNext;
		}
		pTaskInfo = mFrameList;
		while (pTaskInfo && !found)
		{
			if (pTaskInfo->id == id)
			{
				pTaskInfo->status = TASK_DELETE;
				found = true;
				break;
			}
			pTaskInfo = pTaskInfo->pNext;
		}
	}

	void Scheduler::sweepGarbage()
	{
		//
		// Check both tasklist and frame list for tasks that were marked
		// for deletion by the Terminate() method. This implementation is
		// pretty brute-force; garbage collection could be run as an
		// idle processing task.
		//
		//printf("SWEEP BEGIN\n");
		TaskInfo * pTaskInfo = mTaskList;
		TaskInfo * pPrev = NULL;
		while (pTaskInfo)
		{
			if (pTaskInfo->status == TASK_DELETE)
			{
				TaskInfo * pTemp = pTaskInfo;
				pTaskInfo = pTaskInfo->pNext;
				if (pTemp == mTaskList)
					mTaskList = pTaskInfo;
				else
					pPrev->pNext = pTaskInfo;
				//printf("Sched: Deleted %d\n",pTemp->id);
				delete pTemp;
			}
			else
			{
				pPrev = pTaskInfo;
				pTaskInfo = pTaskInfo->pNext;
			}
		}

		pTaskInfo = mFrameList;
		pPrev = NULL;
		while (pTaskInfo)
		{
			if (pTaskInfo->status == TASK_DELETE)
			{
				TaskInfo * pTemp = pTaskInfo;
				pTaskInfo = pTaskInfo->pNext;
				if (pTemp == mFrameList)
					mFrameList = pTaskInfo;
				else
					pPrev->pNext = pTaskInfo;
				//printf("Sched: Deleted %d\n",pTemp->id);
				delete pTemp;
			}
			else
			{
				pPrev = pTaskInfo;
				pTaskInfo = pTaskInfo->pNext;
			}
		}
		//printf("SWEEP END\n");
	}

	int Scheduler::update()
	{
		//printf("EXEC BEGIN\n");
		//
		// Run one frame. This takes the time stamp marking the end of the frame
		// and then processes events for that frame retroactively. This method has
		// the advantage of flexibility, especially if the frame rate fluctuates.
		// However it is always a little behind, because it can't compute the
		// frame length until the end of the frame is reached. With a fixed known
		// frame rate you could optimize things a bit and make the start/end times
		// correspond exactly with real time.
		//
		mClock.beginFrame();
		unsigned started = mClock.getSystem();

		//
		// Execute any time-based tasks
		//
		// (1) Pop the next task off the list. Since the list is always
		//     sorted, the first item in the list is always the next task.
		// (2) Execute it and update times
		// (3) If it's expired, delete it
		//     Otherwise, insert it into the list in its new position
		//
		TaskInfo * pTaskInfo = NULL;
		getNextTimeTask(&pTaskInfo);
		while (pTaskInfo)
		{
			mClock.advanceTo(pTaskInfo->time.next);

			pTaskInfo->pTask->execute(pTaskInfo->id, mClock.getTime(), pTaskInfo->time.period, pTaskInfo->pUser);
			pTaskInfo->time.last = pTaskInfo->time.next;
			pTaskInfo->time.next += pTaskInfo->time.period;

			if (pTaskInfo->time.duration == 0 ||
				pTaskInfo->time.duration >= pTaskInfo->time.next)
			{
				// re-insert into list with updated time
				insertTimeTask(pTaskInfo);
			}
			else
			{
				// task is expired, delete it
				//printf("Sched: Expired %d\n",pTaskInfo->id);
				delete pTaskInfo;
			}
			getNextTimeTask(&pTaskInfo);
		}

		//
		// Advance simulation clock to end of frame
		//
		mClock.advanceToEnd();

		//
		// Now execute all frame tasks in round-robin fashion.
		// Frame tasks always execute at the end of the frame just
		// before rendering. A priority scheme could be used to
		// control sequence. It would be more efficient to keep the
		// list sorted, the same as with time tasks (exe
		//
		pTaskInfo = mFrameList;
		getNextFrameTask(&pTaskInfo);
		//	TaskInfo * pPrev = NULL;
		while (pTaskInfo)
		{
			pTaskInfo->pTask->execute(pTaskInfo->id, mClock.getTime(), pTaskInfo->time.period, pTaskInfo->pUser);
			pTaskInfo->time.last = pTaskInfo->time.next;
			pTaskInfo->time.next += pTaskInfo->time.period;

			if (pTaskInfo->time.duration == 0 ||
				pTaskInfo->time.duration >= pTaskInfo->time.next)
			{
				// re-insert into list with updated time
				insertFrameTask(pTaskInfo);
			}
			else
			{
				// task is expired, delete it
				//printf("Sched: Expired %d\n",pTaskInfo->id);
				delete pTaskInfo;
			}
			getNextFrameTask(&pTaskInfo);
		}

		//
		// render
		//
		if (mRenderTask.pTask != NULL)
			mRenderTask.pTask->execute(mRenderTask.id, mClock.getFrame(), pTaskInfo->time.period, mRenderTask.pUser);

		//
		// here is where we could do idle processing or load balancing
		//
		unsigned elapsed = mClock.getSystem() - started;
		unsigned frameLength = mClock.getFrameEnd() - mClock.getFrameStart();
		//	printf("Busy %u ms, idle %u ms\n", elapsed, frameLength - elapsed);

		//
		// If any tasks are terminated during execution, it is easier to leave
		// them in the list until we're finished iterating through it, then sweep
		// them out later.
		//
		//printf("EXEC END\n");
		sweepGarbage();

		return 0;
	}


}	// namespace
